package com.xj.algorithm.leetcode;

/**
 * 平衡二叉树
 */
public class L110_是否是平衡二叉树 {

    /**
     *给定一个二叉树，判断它是否是高度平衡的二叉树。
     *
     * 本题中，一棵高度平衡二叉树定义为：
     *
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
     *
     * 示例 1:
     * 给定二叉树 [3,9,20,null,null,15,7]
     *
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回 true 。
     *
     * 示例 2:
     * 给定二叉树 [1,2,2,3,3,null,null,4,4]
     *
     *        1
     *       / \
     *      2   2
     *     / \
     *    3   3
     *   / \
     *  4   4
     * 返回 false 。
     */
    public static void main(String[] args) {
        TreeNode root=new TreeNode(3);
        root.left=new TreeNode(9);
        root.right=new TreeNode(20);
        root.right.left=new TreeNode(15);
        root.right.right=new TreeNode(7);
        System.out.println(isBalancedGood(root));

        TreeNode root2=new TreeNode(1);
        root2.left=new TreeNode(2);
        root2.right=new TreeNode(2);
        root2.left.left=new TreeNode(3);
        root2.left.right=new TreeNode(3);
        root2.left.left.left=new TreeNode(4);
        root2.left.left.right=new TreeNode(4);
        System.out.println(isBalancedGood(root2));
    }

    //自己的解法：比较左右子树的最大高度,逐个节点比较左右子树的高度差
    //双重递归，效率差
    public static boolean isBalanced(TreeNode root) {
        if (root==null){
            return true;
        }

        int leftDepth=maxDepth(root.left);
        int rightDepth=maxDepth(root.right);
        if(leftDepth-rightDepth>1 || leftDepth-rightDepth<-1){
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }

    public static int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int result=Math.max(maxDepth(root.left),maxDepth(root.right))+1;
        return result;
    }

    //精彩解法：计算每个节点的作为子树的最大高度。从底至顶（提前阻断法）
    public static boolean isBalancedGood(TreeNode root) {
        return depth(root) != -1;
    }

    //计算当前节点的高度
    public static int depth(TreeNode root) {
        if (root == null) return 0;
        int left = depth(root.left);
        if(left == -1) return -1;
        int right = depth(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }

}
